πŸ“‚ Stack & Queue

@Seongukbaek Posted May 20, 2022 Β· Updated May 20, 2022 Β· 3 min read

🧷 μŠ€νƒ

μž…λ ₯κ³Ό 좜λ ₯이 ν•œ λ°©ν–₯으둜 μ œν•œλ˜λŠ” LIFO(Last in First out, ν›„μž…μ„ μΆœ) ν˜•νƒœμ˜ μ„ ν˜• μžλ£Œκ΅¬μ‘°μ΄λ‹€.

  • λ‚˜μ€‘μ— λ“€μ–΄κ°„ μ›μ†Œκ°€ κ°€μž₯ λ¨Όμ € λ‚˜μ˜€λŠ” 것이 κ°€μž₯ 큰 νŠΉμ§•μ΄λ‹€.
  • μ‹œμŠ€ν…œ ν•΄ν‚Ήμ—μ„œ BufferOverflow 취약점을 μ΄μš©ν•œ 곡격 μ‹œ μŠ€νƒ λ©”λͺ¨λ¦¬μ˜ μ˜μ—­μ—μ„œ μˆ˜ν–‰ν•œλ‹€.

πŸͺš μ‚¬μš©μ‹œκΈ°

  • ν•¨μˆ˜μ˜ Call Stack
  • λ¬Έμžμ—΄ μ—­μˆœ 좜λ ₯
  • μ—°μ‚°μž ν›„μœ„ν‘œκΈ°λ²•
  • DFS
  • μž¬κ·€ ν•¨μˆ˜

🧷 큐

μž…λ ₯κ³Ό 좜λ ₯이 ν•œ μͺ½ 끝(front, rear)으둜 μ œν•œλ˜λŠ” FIFO(First in First out, μ„ μž…μ„ μΆœ) ν˜•νƒœμ˜ μ„ ν˜• μžλ£Œκ΅¬μ‘°μ΄λ‹€.

  • κ°€μž₯ λ¨Όμ € λ“€μ–΄μ˜¨ μ›μ†Œκ°€ κ°€μž₯ λ¨Όμ € λ‚˜μ˜€λŠ” 것이 κ°€μž₯ 큰 νŠΉμ§•μ΄λ‹€.
  • 큐의 κ°€μž₯ 첫 μ›μ†Œλ₯Ό front, 끝 μ›μ†Œλ₯Ό rear 라고 ν•œλ‹€.

    • 큐에 데이터가 λ“€μ–΄μ˜¬ λ•Œ(μ‚½μž… μ—°μ‚°)λŠ” rear 둜 λ“€μ–΄μ˜€κ³ ,
    • 데이터가 λ‚˜κ°ˆ λ•Œ(μ‚­μ œ μ—°μ‚°)λŠ” front 둜 λ‚˜κ°„λ‹€.
  • Java Collectionμ—μ„œ Queue λŠ” μΈν„°νŽ˜μ΄μŠ€μ΄λ‹€. 이λ₯Ό κ΅¬ν˜„ν•˜κ³  μžˆλŠ” PriorityQueue 등을 μ‚¬μš©ν•  수 μžˆλ‹€.

    • μΈν„°νŽ˜μ΄μŠ€μ΄λ―€λ‘œ, 큐 νƒ€μž…μ˜ 객체λ₯Ό 생성할 μˆ˜λŠ” μ—†λ‹€.
    • Queue<Obj> queue = new PriorityQueue<>(); 둜 type-safe 큐λ₯Ό 생성할 수 μžˆλ‹€.

πŸͺš μ‚¬μš©μ‹œκΈ°

  • 버퍼
  • BFS

πŸͺš κ°œμ„ 

크기가 μ •ν•΄μ§„ 일반 νλŠ” 큐에 빈 λ©”λͺ¨λ¦¬κ°€ μžˆμ–΄λ„, 꽉 μ°¨μžˆλŠ” κ²ƒμœΌλ‘œ νŒλ‹¨ν•  수 μžˆλ‹€λŠ” 단점이 μžˆλ‹€. (rear κ°€ 끝에 λ„λ‹¬ν–ˆμ„ λ•Œ, 이전에 pop 된 곡간은 λΉ„μ–΄μžˆμ§€λ§Œ 접근이 λΆˆκ°€λŠ₯ν•˜λ‹€.)

  • 이λ₯Ό "μ›ν˜• 큐"λ₯Ό μ΄μš©ν•΄ κ°œμ„ ν•  수 μžˆλ‹€.
  • λ…Όλ¦¬μ μœΌλ‘œ λ°°μ—΄μ˜ 처음과 끝이 μ—°κ²°λ˜μ–΄ μžˆλŠ” κ²ƒμœΌλ‘œ κ°„μ£Όν•œλ‹€.

μ›ν˜• νλŠ” 초기 곡백 μƒνƒœμΌ λ•Œ front 와 rear κ°€ 0이닀. 곡백, 포화 μƒνƒœλ₯Ό μ‰½κ²Œ κ΅¬λΆ„ν•˜κΈ° μœ„ν•΄ 자리 ν•˜λ‚˜λ₯Ό 항상 λΉ„μ›Œλ‘”λ‹€.

(index + 1) % size둜 μˆœν™˜μ‹œν‚¨λ‹€.

단점

  • λ©”λͺ¨λ¦¬ κ³΅κ°„μ˜ ν™œμš©λ„λŠ” μ˜¬λΌκ°€μ§€λ§Œ, λ°°μ—΄λ‘œ κ΅¬ν˜„λ˜μ–΄ μžˆμ–΄ 큐의 크기가 μ œν•œλœλ‹€.

πŸͺš λ‘λ²ˆμ§Έ κ°œμ„ 

μ—°κ²°λ¦¬μŠ€νŠΈ 큐λ₯Ό μ‚¬μš©ν•΄ 이λ₯Ό κ°œμ„ ν•œλ‹€.

  • 크기가 μ œν•œμ΄ μ—†κ³ ,
  • μ‚½μž… 및 μ‚­μ œ 연산이 νŽΈλ¦¬ν•˜λ‹€.

πŸ“• μ°Έκ³ 

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€